import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

public class DandiaoZhan {
    //选自力扣496.下一个更大的元素
    //nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
    //给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
    //对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。
    // 如果不存在下一个更大元素，那么本次查询的答案是 -1 。
    //返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
    //举例：
    //输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
    //输出：[-1,3,-1]
    //解释：nums1 中每个值的下一个更大元素如下所述：
    //- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
    //- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
    //- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

    //1. 找到递增的栈，栈头到栈底的顺序，从小到大，保持站内的元素是递增的，这样pop出的右边第一个元素
    //就刚好比自己大了
    //2. 注意刚遍历过的元素是从nums2[i]，栈顶元素在nums2数组右边的第一个大的元素是nums2[i](即当前遍历的元素)
    //3. 按照递增栈找到当前比自己大的元素之后，需要在nums1中判断这里的栈顶元素是否存在，
    //利用原先在nums1中的键值对哈希表进行记录，获取原先栈顶元素的下标，将当前对应的值放入新数组当中

    public static int[] nextGreaterElement(int[] nums1, int[] nums2){
        Stack<Integer> temp=new Stack<>();
        int[] res=new int[nums1.length];
        Arrays.fill(res,-1);
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums1.length;i++){
            map.put(nums1[i],i);
        }
        temp.add(0);
        for(int i=0;i< nums2.length;i++){
            if(nums2[i]<=nums2[temp.peek()]){
                temp.add(i);
            }
            else{
                if(!temp.isEmpty()&&nums2[i]>nums2[temp.peek()]){
                    if(map.containsKey(nums2[temp.peek()])){
                        int index=map.get(nums2[temp.peek()]);
                        res[index]=nums2[i];
                    }
                    temp.pop();
                }
                //检查最后的压入更新
                temp.push(i);
            }
        }
        return res;
    }

    // 假设此时再次改一下，改为循环数组，但是需要注意的是在当前的数组中进行操作，按照循环的顺序进行操作
    // 简单的方法是直接将两个数组进行组合遍历
    // 或者是对边界进行判断，将长度*2进行操作
    public static int[] nextTo(int[] nums){
        // 边界判断
        if(nums==null || nums.length<=1){
            return new int[]{-1};
        }
        int size=nums.length;
        int[] result=new int[size]; //存放结果
        Arrays.fill(result,-1);
        Stack<Integer> st=new Stack<>();
        for (int i = 0; i < 2 * size; i++) {
            while(!st.isEmpty()&&nums[i%size]>nums[st.peek()]){
                result[st.peek()]=nums[i%size]; //更新result
                st.pop();
            }
            st.push(i%size);
        }
        return result;
    }
    public static void main(String[] args){
        int[] nums1={4,1,2};
        int[] nums2={1,3,4,2};
        int[] a=nextGreaterElement(nums1,nums2);
        System.out.println("Arrays.toString(a) = " + Arrays.toString(a));
        for(int p:a){
            System.out.print(p+" ");
        }
        System.out.println();
        System.out.println("第二个版本:");
        int[] b=nextTo(nums1);
        System.out.println("Arrays.toString(b) = " + Arrays.toString(b));
    }
}
